Максимални збир на путу кроз матрицу

У табели димензија \(n \times n\) поља су попуњена цифрама од 0 до 9. Играч који се налази у горњем левом углу табеле може да у једном кораку пређе у суседно десно поље или суседно доње поље. Циљ му је да стигне до доњег десног поља тако да збир вредности на пређеним пољима буде максималан. Написати пpограм којим се одређује максималан збир који може да оствари играч при кретању од горњег левог до доњег десног угла.

Улаз

У првој линији стандардног улаза се уноси број редова табеле \(n\) (\(1 \le n \le 30\)), а у следећих \(n\) редова по \(n\) цифара од 0 до 9, раздвојене по једним размаком.

Излаз

У првој линији стандардног излаза приказати тражену вредност максималног збира.

Пример

Улаз

5
4 3 5 7 5
1 9 4 1 3
2 3 5 1 2
1 3 1 2 0
4 6 7 2 1

Излаз

38

Објашњење

Максималан збир се добија када се редом пролазе поља са вредношћу 4 + 3 + 9 + 3 + 3 + 6 + 7 + 2 + 1.